package Hot100;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2021-12-31 16:13
 */
public class reverseList206 {

    /**
     * 206. 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 1、递归
     * 2、直接迭代
     * */
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode last = reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }

    /**
     * 翻转前n个节点
     * */
    ListNode successor=null;
    ListNode reverseN(ListNode head, int n) {
        if (n==1){
            //记录第n+1个节点
            successor=head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);

        head.next.next=head;
        head.next=successor;
        return last;
    }

    /**
     * 92. 反转链表 II
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left==1){
            //相当于翻转前n个元素
            return reverseN(head,right);
        }
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;
    }
}
